package mo.leetcode_top;

import mo.common.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L23 {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        int k = 0;
        List<ListNode> merged = Arrays.asList(lists);
        while (merged.size() >= 2) {
            List<ListNode> result = new ArrayList<>();
            int i = 0;
            int j = merged.size() - 1;
            while (i < j) {
                ListNode tmp = mergeTwoLists(merged.get(i), merged.get(j));
                i++;
                j--;
                result.add(tmp);
            }
            if (merged.size() % 2 != 0) {
                result.add(merged.get(merged.size()/2));
            }
            merged = result;
        }
        return merged.get(0);
    }

    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode sol = new ListNode(-1);
        ListNode current = sol;
        while (list1 != null && list2 != null) {
            while (list1 != null && list1.val <= list2.val) {
                current.next = new ListNode(list1.val);
                current = current.next;
                list1 = list1.next;
            }
            while (list1 != null && list2 != null && list2.val <= list1.val) {
                current.next = new ListNode(list2.val);
                current = current.next;
                list2 = list2.next;
            }
        }
        while (list1 != null) {
            current.next = new ListNode(list1.val);
            current = current.next;
            list1 = list1.next;
        }
        while (list2 != null) {
            current.next = new ListNode(list2.val);
            current = current.next;
            list2 = list2.next;
        }
        return sol.next;
    }


    public static void main(String[] args) {
        L23 test = new L23();
        ListNode l1 = ListNode.convertList2ListNode(Arrays.asList(1, 4, 5));
        ListNode l2 = ListNode.convertList2ListNode(Arrays.asList(1, 3, 5));
        ListNode l3 = ListNode.convertList2ListNode(Arrays.asList(2, 6));
        test.mergeKLists(new ListNode[]{l1, l2, l3}).print();
    }
}
